package pers.qianyu.month_202101.date_20210111;

import org.junit.*;

import java.util.*;

/**
 * 207. 课程表
 * https://leetcode-cn.com/problems/course-schedule/
 * - 拓扑排序
 *
 * @author mizzle rain
 * @date 2021-01-11 22:37
 */
public class CanFinish {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < numCourses; i++) map.put(i, new ArrayList<>());
        int[] edges = new int[numCourses];
        for (int[] p : prerequisites) {
            map.get(p[1]).add(p[0]);
            edges[p[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < edges.length; i++) {
            if (edges[i] == 0) {
                q.offer(i);
            }
        }
        while (!q.isEmpty()) {
            int num = q.poll();
            List<Integer> list = map.get(num);
            for (Integer i : list) {
                edges[i]--;
                if (edges[i] == 0) {
                    q.offer(i);
                }
            }
        }
        for (int item : edges) if (item > 0) return false;
        return true;
    }

    @Test
    public void test1() {
        boolean result = new CanFinish()
                .canFinish(2, new int[][]{{1, 0}});
        System.out.println("result = " + result);
    }
}
